package com.ting.test.algorithms.递归和动态规划.从左往右的模型;


import java.util.ArrayList;

/**
 * 有一组咖啡机，每台制作咖啡的时间不同
 * 假设有一群人同时到达，如何让这群人排队，使得大家都能快速的喝上咖啡
 * 咖啡制作好后，人们一口气就喝完了，喝完一杯咖啡的时间忽略不计
 */
public class 咖啡机问题1 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 7};//数组下标表示咖啡机编号，下标对应的值表示制作一杯咖啡需要的时间
        int[] drinks = new int[10];
        drinks = paidui(arr, drinks);
    }

    /**
     * @param arr    咖啡机
     * @param drinks 排队的人
     * @return 每个排队的人喝完咖啡的时间点
     */
    private static int[] paidui(int[] arr, int[] drinks) {
        SmallHeap smallHeap = new SmallHeap(arr);
        for (int index = 0; index < drinks.length; index++) {
            Elements elements = smallHeap.pop();
            arr[index] = elements.start + elements.cost;
        }
        return arr;
    }


    static class SmallHeap {
        ArrayList<Elements> heap = new ArrayList();
        int size = 0;

        public SmallHeap(int[] arr) {
            for (int cost : arr) {
                heapInsert(0, cost);
            }
        }

        public void heapInsert(int startTime, int cost) {
            heap.add(new Elements(startTime, cost));
            int index = size;
            size++;
            int parent = index / 2 ;
            while (parent >= 0) {
                if (compare(parent, index)) {
                    swap(parent, index);
                }
                index = parent;
                parent = index / 2;
            }
        }

        private void swap(int parent, int index) {
            Elements elements = heap.get(parent);
            heap.set(parent, heap.get(index));
            heap.set(index, elements);
        }

        private boolean compare(int left, int right) {
            return (heap.get(left).start + heap.get(left).cost) > (heap.get(right).start + heap.get(right).cost);
        }

        public Elements pop() {
            Elements elements = heap.get(0);
            swap(0, size - 1);
            heap.remove(size);
            size--;
            return elements;
        }
    }


    static class Elements {
        int start;//咖啡机可以使用的时间点
        int cost;//制作一杯开发需要的耗时

        public Elements(int start, int cost) {
            this.start = start;
            this.cost = cost;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getCost() {
            return cost;
        }

        public void setCost(int cost) {
            this.cost = cost;
        }
    }
}
